import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author 雷明浩
 * @date 2025/7/3 11:08
 */
public class Permutation {
    // 字符串的排列
    // https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3DSQL%25E7%25AF%2587%26topicId%3D295
    private boolean[] vis;
    private ArrayList<String> ret;
    private StringBuilder path;
    public ArrayList<String> Permutation (String str) {
        // write code here
        vis = new boolean[str.length()];
        ret = new ArrayList<String>();
        path = new StringBuilder();
        char[] ss = str.toCharArray();
        Arrays.sort(ss);
        dfs(ss);
        return ret;
    }

    private void dfs(char[] ss) {
        if (path.length() == ss.length) {
            ret.add(path.toString());
            return;
        }
        for (int i = 0; i < ss.length; i++) {
            if (!vis[i]) {
                if (i > 0 && ss[i] == ss[i-1] && !vis[i-1]) {
                    continue;
                } else {
                    vis[i] = true;
                    path.append(ss[i]);
                    dfs(ss);
                    vis[i] = false;
                    path.deleteCharAt(path.length()-1);
                }
            }
        }
    }

    public static void main(String[] args) {
        Permutation p = new Permutation();
        System.out.println(p.Permutation("ab"));
    }
}